package com.zs.letcode.illustration_of_algorithm;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 剑指 Offer 38. 字符串的排列
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * <p>
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 * <p>
 * 示例:
 * <p>
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 * 限制：
 * <p>
 * 1 <= s 的长度 <= 8
 * <p>
 * 相关标签
 * 字符串
 * 回溯
 * <p>
 * Python3
 * <p>
 * <p>
 * <p>
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dfv5h/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/19 08:19
 */
public class Chapter33 {
    public static void main(String[] args) {

    }

    private class Solution {
        List<String> res = new ArrayList<>();
        char[] c;

        public String[] permutation(String s) {
            c = s.toCharArray();
            dfs(0);
            return res.toArray(new String[res.size()]);
        }

        private void dfs(int x) {
            if (x == c.length - 1) {
                res.add(String.valueOf(c));
                return;
            }
            Set<Character> set = new HashSet<>();
            for (int i = x; i < c.length; i++) {
                if (set.contains(c[i])) continue;
                set.add(c[i]);
                swap(i, x);
                dfs(x + 1);
                swap(i, x);
            }
        }

        void swap(int a, int b) {
            char tmp = c[a];
            c[a] = c[b];
            c[b] = tmp;
        }
    }
}
